public class Solution {

    // 二分查找
    public boolean binaryFind(int[] arr, int left, int right, int tar){
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] == tar) {
                return true;
            }
            else if (arr[mid] > tar) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return false; 
    }


    public boolean Find(int target, int [][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return false;
        }
        
        // 二分查找
        /*
        for (int i = 0; i < array.length; i++) {
            if (binaryFind(array[i], 0, array[i].length - 1, target)) {
                return true;
            }
        }
        return false;
        */

        // 线性特征
        int row = array.length - 1;
        int col = 0;
        while (row >= 0 && col < array[0].length) {
            if (array[row][col] == target) {
                return true;
            }
            else if (array[row][col] > target) {
                row--;
            }
            else {
                col++;
            }
        }
        return false;

       
    }
}
